Optimization

Quadratic Unconstrained Binary Optimization (QUBO) problems

QUBO problems are among the most widely used methods for solving classical optimization problems on quantum computers, and they are also one of the most interesting optimization challenges. These problems are generally NP-hard, requiring the identification of a binary vector \(\boldsymbol{x} \in \left\{0, 1\right\}^{n}\) that minimizes the following quadratic cost function:

\[\begin{equation} f\left(\boldsymbol{x}\right) = \boldsymbol{x}^T \ \mathcal{Q} \ \boldsymbol{x} = \sum\limits_{j=1}^n \sum\limits_{j^{\prime}=j}^n \mathcal{Q}_{jj^{\prime}} \ x_j \ x_{j}^{\prime} \end{equation}\]

where \(n\) is the number of optimization binary variables involved in the problem.

A QUBO problem is fully defined by its QUBO matrix \(\mathcal{Q}\), a square symmetric matrix. The diagonal elements, \(\mathcal{Q}_{jj}\), represent the self-interaction (or local bias) of each binary variable \(x_j\), while the off-diagonal ones describe the pair-interactions between different binaries. As the QUBO matrix is symmetric, we can limit the computations to its upper triangular part, as defined by the equation above.

The module contains both exact and tensor-network based solvers for a generic QUBO problem in a standard format.

class qtealeaves.optimization.qubo_solver.QUBOConvergenceParameter(max_bond_dimension=8, max_iter=20, abs_deviation=4e-12, rel_deviation=1e-12, n_points_conv_check=6, random_sweeps=False, enable_spacelink_expansion=False, arnoldi_maxiter=32, psi0='random', ini_bond_dimension=None, psi0_noise=1e-07, transverse_field_ratio=0, tn_input_folder_path='./Tensor_Network_Simulation_Inputs/', tn_output_folder_path='./Tensor_Network_Simulation_Outputs/', tn_sampling_folder_path='./Tensor_Network_Simulation_States/', tn_io_extra_tag=None, tn_type=5, data_type='C', optimization_level=-1, device='cpu', **kwargs)

Convergence parameters for the QUBO solver. An instance of this class must be created and passed to the QUBO solver whenever the QUBO problem is to be solved using tensor networks.

max_bond_dimensionint, optional

The maximum bond dimension of the tensor network during the ground-state search. The maximum value of the bond dimension is upper bounded by \(2^{n \mathbin{//} 2}\), where \(n\) is the number of spins in the spin glass system. Default to 8.

max_iterint, optional

The maximum number of sweeps for the ground-state search. After max_iter the ground-state search ends. Default to 20 sweeps.

abs_deviationfloat, optional

Exit criterion for the ground-state search. If the energy of the current sweep has an absolute per-sweep deviation from the previous sweeps below this threshold, the tensor network optimization ends. Default to 4e-12.

rel_deviationfloat, optional

Exit criterion for ground-state search. If the energy of the current sweep has a relative per-sweep deviation from the previous sweeps below this threshold, the tensor network optimization ends. Default to 1e-12.

n_points_conv_checkint, optional

The number of sweeps used when checking convergence for the ground state search. Exit criteria are not checked until this many sweeps have been performed. Default to 6.

random_sweepsbool, optional

If True, perform random sweeps to optimize the tensors. Default to False.

enable_spacelink_expansionbool, optional

The mode used for sweeping along the tensors during the optimization. If False, standard sweeps without space link expansion are performed to obtain the ground state; if True, the first half of the sweeps use space link expansion, while in the second half the space link expansion is disabled. Default to False.

arnoldi_maxiterint, optional

Maximum number of Lanczos vectors to be used in the eigensolver. Default to 32.

psi0str, optional

The initial tensor network state from which to start the ground-state search for the spin glass Hamiltonian representing the QUBO problem. The available options are:

• random: the initial state of the tensors is initialized randomly; - exact_driver_product_state: the tensors are initialized in the product state

  :math:`left

ert{+} ight angle^{n}`

\[\left\]

ert{+} ight angle

= dfrac{1}{sqrt{2}} left(left

ert{0} ight angle

left

ert{1} ight angle ight)

i.e., in the ground state of the driver Hamiltonian

\[\mathcal{H}_{\scriptscriptstyle driver} = \sum\limits_{j=1}^n \sigma_j^x .\]

Within this option, the product state is exactly constructed with the given initial bond dimension \(\chi =\) init_bond_dimension;

• ‘tn_driver_product_state’: the tensors are initialized in the ground state of \(\mathcal{H}_{\scriptscriptstyle driver}\) obtained via a ground-state search of the corresponding driver Hamiltonian with bond dimension \(\chi =\) init_bond_dimension. Default to random.

ini_bond_dimensionint, optional

The bond dimension used to construct the initial tensor network state. Using subspace expansion the bond dimension can grow. Default to None, i.e., the initial bond dimension is initialized to max_bond_dimension.

psi0_noisefloat, optional

Numerical noise to construct the exact initial product state with a given bond dimension. More details can be found in the opt_tooling submodule. Default to 1e-7.

transverse_field_ratiofloat, optional

The ratio of the magnitude of the strength of the classical longitudinal terms (Z-Pauli) to the quantum off-diagonal transverse field terms (X-Pauli) to be added. This ratio controls the magnitude of the transverse field perturbation relative to the classical Hamiltonian, whose ground state must be determined. See the function generate_perturbation_transverse_fields() in the opt_tooling submodule. Default to 0, i.e., no transverse fields will be added to the classical Hamiltonian.

tn_input_folder_pathstr, optional

The full path where to save the input data and parameters for the tensor network ground-state search. If the folder does not exist, it will be automatically created. Default to /Tensor_Network_Simulation_Inputs/.

tn_output_folder_pathstr, optional

The full path where to save the output data and log files for the tensor network ground-state search. If the folder does not exist, it will be automatically created. Default to /Tensor_Network_Simulation_Outputs/.

tn_sampling_folder_pathstr, optional

The full path where to save the tensor network states for the OPES sampling. If the folder does not exist, it will be automatically created. Default to /Tensor_Network_Simulation_States/.

tn_io_extra_tagstr, optional

Extra common tag to be added at the end of simulation log files in order to distringuish different simulations. Default to None.

data_typestr, optional

Data type of the tensors in the chosen ansatz. Available options are

• “A”: automatic

• “Z”: double precision complex (.complex128)

• “C”: single precision complex (.complex64)

• “D”: double precision real (.float64)

• “S”: single precision real (.float32)

Default to C.

tn_typeint, optional

The ansatz to be used for approximating the wave function of the mapped spin glass system. Available topologies are TTN (use 5) for Tree Tensor Networks and MPS (use 6) for Matrix Product States. Default to TTN (5).

optimization_levelint, optional

Optimization level for the tensor network simulation, i.e., the MPO representation inside the tensor network simulation. To enforce cache for sampling input 1, or to use TPO (iTPO with compression) input 0 (3). Default to -1, which enables an auto-selection.

devicestr, optional

Device where to run the optimization. Available options are cpu to run the ground-state search on the CPUs, and gpu to run the ground-state search on the GPUs. Default to cpu.

class qtealeaves.optimization.qubo_solver.QUBOSolver(qubo_matrix)

Solver for a generic QUBO problem

\[\begin{split}\\min\\limits_{x \in \\left\{0, 1\right\}^n} f(\\boldsymbol{x})\end{split}\]

\[\begin{split}f(\\boldsymbol{x}) = \\boldsymbol{x}^T \\mathcal{Q} \\boldsymbol{x}\end{split}\]

where \(\boldsymbol{x}\) is the \(n\)-dimensional binary vector describing the binary configuration of the QUBO decision variables. The QUBO problem is uniquely described by the QUBO matrix \(\\mathcal{Q}\), which must be a symmetric or upper triangular real matrix.

This QUBO solver implements different methods to obtain a solution:

• brute-force obtains the exact solution (global optimum) but it’s limited by the number of binaries (\(n \\leq 30\));

• exact ground-state search maps the QUBO problem into an equivalent spin glass Hamiltonian and encodes the QUBO solution into the ground state of this Hamiltonian. The ground state is exactly reconstructed by creating the full Hamiltonian matrix and sorting its diagonal. This method obtains the exact solution (global optimum), but it’s limited by the number of binaries (\(n \\leq 30\), depending on the available RAM);

• tensor-network based ground-state search also maps the QUBO problem into a corresponding ground-state search of a spin glass Hamiltonian, but the solution is found by applying tensor-network optimization using tools from qtealeaves. This solver is not limited by the number of binaries but by the amount of entanglement needed for the computation.

Parameters

qubo_matrixnp.ndarray[float]

The input QUBO problem represented by its QUBO matrix. The input matrix must be either a symmetric or and upper triangular 2D numpy array of real numbers. Only the upper triangular part of the input matrix will be considered, i.e., if \(Q_{ij}\) are the matrix elements of the input QUBO problem, only those for \(i \\leq j\) will be used by the solver.

evaluate(binaries_configuration)

Evaluate the QUBO cost function for a given binaries configuration. The QUBO cost function is defined as

\[\begin{split}f_{\\mathrm{\\scriptscriptstyle QUBO}} = \\sum\nolimits_{j < j^{\prime} = 1}^n Q_{j j^{\prime}} x_j x_{j^{\prime}} + \\sum\nolimits_{j=1}^n Q_{jj} x_j\end{split}\]

where \(n\) is the number of binary decision variables in the QUBO problem and \(\\mathcal{Q}\) is the QUBO matrix.

Arguments

binaries_configurationList[int]

The \(n\)-dimensional bitstring representing the given decision variables in the QUBO configuration.

Returns

costfloat

The value of the QUBO cost function for the given binaries configuration.

prettyprint()

Pretty print method to visualize the QUBO matrix to standard output.

Arguments

None

Returns

None

classmethod read(filename)

Initialize the QUBO problem from an input file.

Arguments

filenamestr

The full path to the file containing the QUBO problem as a matrix in a given (allowed) format. A check on file’s extension is performed before reading.

Returns

objqtealeaves.optimization.QUBOSolver

The created QUBO solver object.

static renormalize_spinglass_couplings(spinglass_couplings, max_diff=100)

Rescale the couplings (local biases and two-spin interaction strengths) of the spin glass model associated with the QUBO matrix to the range [-1, 1] whenever the difference between the largest and the smallest value of the couplings exceeds max_diff.

Arguments

spinglass_couplingsDict

The set of couplings defining the corresponding spin glass Hamiltonian, specifically:

• ‘offset’: the constant term proportional

  to the identity. This energy offset does not influence the solution of the QUBO problem, but it is necessary to reconstruct the exact value of the QUBO cost function, e.g., from the ground-state energy;

• ‘one-body’: the set of single-body couplings,

  i.e., the set of local longitudinal magnetic fields (biases), one for each spin-1/2 in the spin glass system;

• ‘two-body’: the set of two-body (in general all-to-all)

  couplings describing the interactions between pairs of spin-1/2.

max_difffloat, optional

If the difference between the largest and the smallest values of the coupling strengths exceeds this number, the spin glass couplings are rescaled to [-1, 1]. Default to 100.

Returns

rescaled_couplingsDict

The set of rescaled couplings defining the corresponding spin glass Hamiltonian, specifically:

• ‘offset’: the constant term proportional

  to the identity. The offset is not affected by the rescaling;

• ‘max’: the rescaling factor to get back the original

  spin glass Hamiltonian couplings;

• ‘one-body’: the set of rescaled single-body couplings,

  i.e., the set of local longitudinal magnetic fields (biases), one for each spin-1/2 in the spin glass system;

• ‘two-body’: the set of rescaled two-body (in general

  all-to-all) couplings describing the interactions between pairs of spin-1/2.

save_to_file(filename, ftype)

Save the QUBO matrix to a log file.

Arguments

filenamestr

The full path (without the extension) to the log file where the QUBO matrix will be written in the specified ftype extension.

ftypestr, optional

The (allowed) extension of the output log file.

Returns

None

solve(solver='tensor-network', n_solutions=1, rescale_couplings=True, tn_convergence_parameters=None, tensor_backend=<qtealeaves.tensors.tensor_backend.TensorBackend object>)

Solve the QUBO problem with a specific solver.

Arguments

solverstr, optional

The method to be used for performing the ground-state search of the mapped spin glass Hamiltonian. Options are tensor-network, exact and brute-force. Default to tensor-network.

n_solutionsint, optional

The number of optimal or near-optimal solutions to be computed with the given solver. Default to 1, i.e., the solver searches only for the ground state of the mapped spin glass Hamiltonian. This arguments does not affect the brute-force solver.

rescale_couplingsbool, optional

If True, the couplings defining the corresponding spin glass model are rescaled in [-1, 1]. This arguments does not affect the brute-force solver. Default to True.

tn_convergence_paramsinstance of QUBOConvergenceParameter

The convergence parameters for the QUBO solver simulation based on tensor network methods. Default to None, meaning no tensor network method is used to solve the QUBO.

tensor_backendqtealeaves.tensors.TensorBackend, optional

Setup for tensor backend that defines the complete backend to be used for the tensors. Default to TensorBackend(), meaning that the underlying class for tensors is qtealeaves.tensors.QteaTensor, the device for both the memory and the computations is the CPU and the data type of the tensors is np.complex128, i.e., double precision complex. You can pass different backend for the tensor class, for example pytorch running on GPUs, or use a mixed device for memory and computations with CPU + GPU. More details can be found both in qtealeaves and qredtea.

Returns

None

solve_via_brute_force()

Solve the QUBO problem via brute force by generating all the possible decision binary configurations. This solver is, of course, limited to problem sizes less than 30 binaries. No mapping to a spin glass is needed for this solver.

Arguments

None

Returns

None

solve_via_exact_sorting(spinglass_model, n_solutions=1)

Find the optimal solution(s) to the QUBO problem by mapping it onto a spin glass Hamiltonian. Then, find the ground-state (or low-energy eigenstates) of this Hamiltonian by performing an exact sorting of its diagonal.

Arguments

spinglass_modelDict

The set of couplings defining the corresponding spin glass Hamiltonian. For more details, see to_spinglass_couplings().

n_solutionsint, optional

The number of optimal solutions to the QUBO to be computed, i.e., the number of eigenstates to be extracted from the ordered spin glass spectrum.

Returns

None

solve_via_tn_ground_state_search(spinglass_model, convergence_params, n_eigenstates=1, tensor_backend=<qtealeaves.tensors.tensor_backend.TensorBackend object>)

Find the optimal solution(s) to the QUBO problem by mapping it onto a spin glass Hamiltonian. Then, find the ground-state (or low-energy eigenstates) of this Hamiltonian by performing a variational optimization via tensor-network methods. Specifically, the wave function of the spin glass system is represented as a tensor network (TN) with a given topology and bond dimension, and the energy is optimized using numerical methods from qtealeaves.

Arguments

spinglass_modelDict

The set of couplings defining the corresponding spin glass Hamiltonian. For more details, see to_spinglass_couplings().

convergence_paramsinstance of QUBOConvergenceParameter

The convergence parameters for the QUBO solver simulation, for example the bond dimension, the number of sweeps, and the initial tensor network state.

n_eigenstatesint, optional

The number of optimal solutions to the QUBO problem to be computed, i.e., the number of eigenstates to be extracted from the spin glass spectrum. Default to 1, i.e., only the ground state. If greater than 1, excited states are obtained via sampling of spin configurations from the converged tensor network state. In this case, there is no guarantee that the sampled states are exactly the first n_eigenstates eigenvectors in the Hamiltonian spectrum (in general, they don’t).

tensor_backendqtealeaves.tensors.TensorBackend, optional

Setup for tensor backend that defines the complete backend to be used for the tensors. Default to TensorBackend(), meaning that the underlying class for tensors is qtealeaves.tensors.QteaTensor, the device for both the memory and the computations is the CPU and the data type of the tensors is np.complex128, i.e., double precision complex. You can pass different backend for the tensor class, for example pytorch running on GPUs, or use a mixed device for memory and computations with CPU + GPU. More details can be found both in qtealeaves and qredtea.

Returns

None

static spin_to_binary_config(spin_configuration)

Implement the conversion from spin 1/2 variables to binary variables to recover a QUBO problem bitstring. The linear transformation

• \(x = \\dfrac{1 + \\sigma}{2}\)

• \(x \in \\left\{0, 1\right\}\) (binary variable)

• \(\\sigma \in \\left\{+1, -1\right\}\) (qubit variable`

maps the 0-bit into spin-down and the 1-bit into spin-up.

Arguments

spin_configurationList[int]

The configuration of +1 and -1 representing the quantum expectation value of the Z-Pauli matrix on each site of the spin glass model (+1 means spin-up while -1 mean spin-down).

Returns

bitstringList[int]

The converted string of 0s and 1s.

to_spinglass_couplings()

Derive the corresponding spin glass model of the QUBO problem. The couplings of the spin glass Hamiltonian are obtained from the QUBO matrix elements by transforming binary variables to spin-1/2 variables (0 –> -1, 1 –> +1).

Arguments

None

Returns

spinglass_couplingsDict

The set of couplings defining the corresponding spin glass Hamiltonian, specifically:

• ‘offset’: the constant term proportional

  to the identity. This energy offset does not influence the solution of the QUBO problem, but it is necessary to reconstruct the exact value of the QUBO cost function, e.g., from the ground-state energy;

• ‘one-body’: the set of single-body couplings,

  i.e., the set of local longitudinal magnetic fields (biases), one for each spin-1/2 in the spin glass system;

• ‘two-body’: the set of two-body (in general all-to-all)

  couplings describing the interactions between pairs of spin-1/2.

Tensor-network based QUBO solver

The approach implemented in this sub-module is based on the ground-state search algorithm from qtealeaves and involves the following steps:

• The defined QUBO problem, represented by the \(\mathcal{Q}\) matrix, is mapped to an equivalent ground-state search problem of the following spin glass Hamiltonian:

  \[\begin{equation} \mathcal{H} = \sum\limits_{j=1}^n h_j \sigma_j + \sum\limits_{j=1}^n \sum\limits_{j^{\prime}=j+1}^n \mathcal{J}_{jj^{\prime}} \sigma_j \sigma_{j^{\prime}} \end{equation}\]

  where the spin glass couplings can be obtained from the QUBO matrix elements. This mapping is achieved through the following simple linear invertible transformation:

  \[\begin{equation} \sigma_j = 2 x_j - 1 \end{equation}\]

  which maps each QUBO binary variable \(x_j \in \left\{0, 1\right\}\) into a spin-\(1\mathbin{/}2\) variable \(\sigma_j \in \left\{-1, +1\right\}\).

• After constructing the Hamiltonian and representing it as a tensor network operator, the qtealeaves QUBO solver applies the ground-state search algorithm to find the ground state. Once the ground state is found, the mapping is reversed to reconstruct the solution bitstring, and the cost function value is calculated for the optimized bitstring.

Several exact solvers are also implemented to benchmark the tensor network solution for small instances.

The tensor network ansatz used to represent the wave function of the spin glass Hamiltonian is the Tree Tensor Network (TTN).

Various options for the ground-state search are available.

class qtealeaves.optimization.QUBOSolver(qubo_matrix)

Solver for a generic QUBO problem

\[\begin{split}\\min\\limits_{x \in \\left\{0, 1\right\}^n} f(\\boldsymbol{x})\end{split}\]

\[\begin{split}f(\\boldsymbol{x}) = \\boldsymbol{x}^T \\mathcal{Q} \\boldsymbol{x}\end{split}\]

where \(\boldsymbol{x}\) is the \(n\)-dimensional binary vector describing the binary configuration of the QUBO decision variables. The QUBO problem is uniquely described by the QUBO matrix \(\\mathcal{Q}\), which must be a symmetric or upper triangular real matrix.

This QUBO solver implements different methods to obtain a solution:

• brute-force obtains the exact solution (global optimum) but it’s limited by the number of binaries (\(n \\leq 30\));

• exact ground-state search maps the QUBO problem into an equivalent spin glass Hamiltonian and encodes the QUBO solution into the ground state of this Hamiltonian. The ground state is exactly reconstructed by creating the full Hamiltonian matrix and sorting its diagonal. This method obtains the exact solution (global optimum), but it’s limited by the number of binaries (\(n \\leq 30\), depending on the available RAM);

• tensor-network based ground-state search also maps the QUBO problem into a corresponding ground-state search of a spin glass Hamiltonian, but the solution is found by applying tensor-network optimization using tools from qtealeaves. This solver is not limited by the number of binaries but by the amount of entanglement needed for the computation.

Parameters

qubo_matrixnp.ndarray[float]

The input QUBO problem represented by its QUBO matrix. The input matrix must be either a symmetric or and upper triangular 2D numpy array of real numbers. Only the upper triangular part of the input matrix will be considered, i.e., if \(Q_{ij}\) are the matrix elements of the input QUBO problem, only those for \(i \\leq j\) will be used by the solver.

evaluate(binaries_configuration)

Evaluate the QUBO cost function for a given binaries configuration. The QUBO cost function is defined as

\[\begin{split}f_{\\mathrm{\\scriptscriptstyle QUBO}} = \\sum\nolimits_{j < j^{\prime} = 1}^n Q_{j j^{\prime}} x_j x_{j^{\prime}} + \\sum\nolimits_{j=1}^n Q_{jj} x_j\end{split}\]

where \(n\) is the number of binary decision variables in the QUBO problem and \(\\mathcal{Q}\) is the QUBO matrix.

Arguments

binaries_configurationList[int]

The \(n\)-dimensional bitstring representing the given decision variables in the QUBO configuration.

Returns

costfloat

The value of the QUBO cost function for the given binaries configuration.

prettyprint()

Pretty print method to visualize the QUBO matrix to standard output.

Arguments

None

Returns

None

classmethod read(filename)

Initialize the QUBO problem from an input file.

Arguments

filenamestr

The full path to the file containing the QUBO problem as a matrix in a given (allowed) format. A check on file’s extension is performed before reading.

Returns

objqtealeaves.optimization.QUBOSolver

The created QUBO solver object.

static renormalize_spinglass_couplings(spinglass_couplings, max_diff=100)

Rescale the couplings (local biases and two-spin interaction strengths) of the spin glass model associated with the QUBO matrix to the range [-1, 1] whenever the difference between the largest and the smallest value of the couplings exceeds max_diff.

Arguments

spinglass_couplingsDict

The set of couplings defining the corresponding spin glass Hamiltonian, specifically:

• ‘offset’: the constant term proportional

  to the identity. This energy offset does not influence the solution of the QUBO problem, but it is necessary to reconstruct the exact value of the QUBO cost function, e.g., from the ground-state energy;

• ‘one-body’: the set of single-body couplings,

  i.e., the set of local longitudinal magnetic fields (biases), one for each spin-1/2 in the spin glass system;

• ‘two-body’: the set of two-body (in general all-to-all)

  couplings describing the interactions between pairs of spin-1/2.

max_difffloat, optional

If the difference between the largest and the smallest values of the coupling strengths exceeds this number, the spin glass couplings are rescaled to [-1, 1]. Default to 100.

Returns

rescaled_couplingsDict

The set of rescaled couplings defining the corresponding spin glass Hamiltonian, specifically:

• ‘offset’: the constant term proportional

  to the identity. The offset is not affected by the rescaling;

• ‘max’: the rescaling factor to get back the original

  spin glass Hamiltonian couplings;

• ‘one-body’: the set of rescaled single-body couplings,

  i.e., the set of local longitudinal magnetic fields (biases), one for each spin-1/2 in the spin glass system;

• ‘two-body’: the set of rescaled two-body (in general

  all-to-all) couplings describing the interactions between pairs of spin-1/2.

save_to_file(filename, ftype)

Save the QUBO matrix to a log file.

Arguments

filenamestr

The full path (without the extension) to the log file where the QUBO matrix will be written in the specified ftype extension.

ftypestr, optional

The (allowed) extension of the output log file.

Returns

None

solve(solver='tensor-network', n_solutions=1, rescale_couplings=True, tn_convergence_parameters=None, tensor_backend=<qtealeaves.tensors.tensor_backend.TensorBackend object>)

Solve the QUBO problem with a specific solver.

Arguments

solverstr, optional

The method to be used for performing the ground-state search of the mapped spin glass Hamiltonian. Options are tensor-network, exact and brute-force. Default to tensor-network.

n_solutionsint, optional

The number of optimal or near-optimal solutions to be computed with the given solver. Default to 1, i.e., the solver searches only for the ground state of the mapped spin glass Hamiltonian. This arguments does not affect the brute-force solver.

rescale_couplingsbool, optional

If True, the couplings defining the corresponding spin glass model are rescaled in [-1, 1]. This arguments does not affect the brute-force solver. Default to True.

tn_convergence_paramsinstance of QUBOConvergenceParameter

The convergence parameters for the QUBO solver simulation based on tensor network methods. Default to None, meaning no tensor network method is used to solve the QUBO.

tensor_backendqtealeaves.tensors.TensorBackend, optional

Setup for tensor backend that defines the complete backend to be used for the tensors. Default to TensorBackend(), meaning that the underlying class for tensors is qtealeaves.tensors.QteaTensor, the device for both the memory and the computations is the CPU and the data type of the tensors is np.complex128, i.e., double precision complex. You can pass different backend for the tensor class, for example pytorch running on GPUs, or use a mixed device for memory and computations with CPU + GPU. More details can be found both in qtealeaves and qredtea.

Returns

None

solve_via_brute_force()

Solve the QUBO problem via brute force by generating all the possible decision binary configurations. This solver is, of course, limited to problem sizes less than 30 binaries. No mapping to a spin glass is needed for this solver.

Arguments

None

Returns

None

solve_via_exact_sorting(spinglass_model, n_solutions=1)

Find the optimal solution(s) to the QUBO problem by mapping it onto a spin glass Hamiltonian. Then, find the ground-state (or low-energy eigenstates) of this Hamiltonian by performing an exact sorting of its diagonal.

Arguments

spinglass_modelDict

The set of couplings defining the corresponding spin glass Hamiltonian. For more details, see to_spinglass_couplings().

n_solutionsint, optional

The number of optimal solutions to the QUBO to be computed, i.e., the number of eigenstates to be extracted from the ordered spin glass spectrum.

Returns

None

solve_via_tn_ground_state_search(spinglass_model, convergence_params, n_eigenstates=1, tensor_backend=<qtealeaves.tensors.tensor_backend.TensorBackend object>)

Find the optimal solution(s) to the QUBO problem by mapping it onto a spin glass Hamiltonian. Then, find the ground-state (or low-energy eigenstates) of this Hamiltonian by performing a variational optimization via tensor-network methods. Specifically, the wave function of the spin glass system is represented as a tensor network (TN) with a given topology and bond dimension, and the energy is optimized using numerical methods from qtealeaves.

Arguments

spinglass_modelDict

The set of couplings defining the corresponding spin glass Hamiltonian. For more details, see to_spinglass_couplings().

convergence_paramsinstance of QUBOConvergenceParameter

The convergence parameters for the QUBO solver simulation, for example the bond dimension, the number of sweeps, and the initial tensor network state.

n_eigenstatesint, optional

The number of optimal solutions to the QUBO problem to be computed, i.e., the number of eigenstates to be extracted from the spin glass spectrum. Default to 1, i.e., only the ground state. If greater than 1, excited states are obtained via sampling of spin configurations from the converged tensor network state. In this case, there is no guarantee that the sampled states are exactly the first n_eigenstates eigenvectors in the Hamiltonian spectrum (in general, they don’t).

tensor_backendqtealeaves.tensors.TensorBackend, optional

Setup for tensor backend that defines the complete backend to be used for the tensors. Default to TensorBackend(), meaning that the underlying class for tensors is qtealeaves.tensors.QteaTensor, the device for both the memory and the computations is the CPU and the data type of the tensors is np.complex128, i.e., double precision complex. You can pass different backend for the tensor class, for example pytorch running on GPUs, or use a mixed device for memory and computations with CPU + GPU. More details can be found both in qtealeaves and qredtea.

Returns

None

static spin_to_binary_config(spin_configuration)

Implement the conversion from spin 1/2 variables to binary variables to recover a QUBO problem bitstring. The linear transformation

• \(x = \\dfrac{1 + \\sigma}{2}\)

• \(x \in \\left\{0, 1\right\}\) (binary variable)

• \(\\sigma \in \\left\{+1, -1\right\}\) (qubit variable`

maps the 0-bit into spin-down and the 1-bit into spin-up.

Arguments

spin_configurationList[int]

The configuration of +1 and -1 representing the quantum expectation value of the Z-Pauli matrix on each site of the spin glass model (+1 means spin-up while -1 mean spin-down).

Returns

bitstringList[int]

The converted string of 0s and 1s.

to_spinglass_couplings()

Derive the corresponding spin glass model of the QUBO problem. The couplings of the spin glass Hamiltonian are obtained from the QUBO matrix elements by transforming binary variables to spin-1/2 variables (0 –> -1, 1 –> +1).

Arguments

None

Returns

spinglass_couplingsDict

The set of couplings defining the corresponding spin glass Hamiltonian, specifically:

• ‘offset’: the constant term proportional

  to the identity. This energy offset does not influence the solution of the QUBO problem, but it is necessary to reconstruct the exact value of the QUBO cost function, e.g., from the ground-state energy;

• ‘one-body’: the set of single-body couplings,

  i.e., the set of local longitudinal magnetic fields (biases), one for each spin-1/2 in the spin glass system;

• ‘two-body’: the set of two-body (in general all-to-all)

  couplings describing the interactions between pairs of spin-1/2.

class qtealeaves.optimization.qubo_solver.QUBOProblemError

Custom derived exception class for errors in the QUBO solver instantiation process.

Optimization tooling

Sub-module that implements tools and support methods for the QUBO solver class.

class qtealeaves.optimization.create_exact_observables(number_of_spins)

Construct the observables as many-body operators represented as sparse matrices.

Arguments

number_of_spinsint

The number of spins in the system.

Returns

observablesDict

A dictionary containing the observables as 2D sparse scipy matrices. The name of the observable is the key, the operator matrix representing the observable is the value.

class qtealeaves.optimization.create_exact_spinglass_hamiltonian(spinglass_couplings, one_body_terms_prefactor=1.0, two_body_terms_prefactor=1.0)

Construct the exact 2D matrix representation of a spin glass Hamiltonian operator characterized by spinglass_couplings.

Arguments

spinglass_couplingsDict

The set of couplings defining the spin glass Hamiltonian, specifically

• ‘offset’: the constant term proportional

  to the identity. This energy offset does not influence the spectrum of the spin glass system, but it is necessary to reconstruct the exact energy values of the eigenstates encoding spin configurations,

• ‘one-body’: the set of single-body couplings,

  i.e., the set of local longitudinal magnetic fields (biases), one for each spin-1/2 in the spin glass system;

• ‘two-body’: the set of two-body (in general all-to-all)

  couplings describing the interactions between pairs of spin-1/2.

one_body_terms_prefactorfloat, optional

The multiplicative prefactor of the spin glass local biases terms. Default to 1.0.

two_body_terms_prefactorfloat, optional

The multiplicative prefactor of the spin-spin interaction-strength terms. Default to 1.0.

Returns

ham_matrixcsr_matrix[float]

The 2D scipy sparse matrix representing the spin glass Hamiltonian matrix as a many-body operator.

class qtealeaves.optimization.compute_exact_spectrum(ham_matrix, number_of_eigenstates=1)

Compute the exact spectrum of a many-body classical Hamiltonian. The following implementation stems directly from the classical nature of the Hamiltonian, indicating that the matrix representing the Hamiltonian operator is diagonal in the chosen (computational) basis.

Arguments

ham_matrixcsr_matrix[float]

The 2D scipy sparse matrix representing the Hamiltonian operator.

number_of_eigenstatesint, optional

The fist number_of_eigenstate states to be computed. Default to 1, i.e., only the ground state.

Returns

spectrumList[List[float, np.ndarray[float]]]

The target number of eigenstates and associated exact energies in the Hamiltonian spectrum. The output is a list of exact [energy, eigenstate] sorted in ascending order w.r.t. the energy values.

class qtealeaves.optimization.measure_exact_observables(observables, exact_spectrum)

Measure observables on the exact eigenstates of a classical many-body Hamiltonian.

Arguments

observables: Dict

The dictionary that holds information on the observables to be measured as many-body operators. See for example create_exact_observables()

exact_spectrumList[List[float, np.ndarray[float]]]

The set of lists [energy, eigenvector] obtained via the exact computation of a classical many-body Hamiltonian. See for example compute_exact_spectrum().

Returns

expectation_valuesDict

The dictionary that contains the quantum average of each observable to be measured on the exact eigenstates of the many-body Hamiltonian, i.e.,

\[\left\langle \psi \left\vert \mathcal{O} \right\vert \psi \right\rangle\]

where \(\mathcal{O}\) is the quantum operrator representing the desired observables.

class qtealeaves.optimization.generate_perturbation_transverse_fields(model_local_hfields, ratio, sign_mode='random')

Generate a set of local random inhomogeneous transverse fields to add a quantum X-Pauli term at each site to the classical spin glass Hamiltonian. This could improve the ground-state search via tensor network optimization, helping to escape local minima of the glassy energy landscape. These transverse fields are randomly drawn, with their magnitude determined by the average value of the local longitudinal magnetic fields, i.e., the spin glass local biases of the classical Hamiltonian.

Arguments

model_local_hfieldsnp.ndarray[float]

The set of local longitudinal magnetic fields, i.e., the local spin glass biases, related to the classical Z-Pauli terms in the classical spin glass Hamiltonian.

ratiofloat

The ratio of the magnitude of the strength of the classical longitudinal terms (Z-Pauli) to the quantum off-diagonal transverse field terms (X-Pauli) to be added. This ratio controls the magnitude of the transverse field perturbation relative to the classical Hamiltonian, whose ground state must be determined.

sign_modestr, optional

The sign of the local random transverse fields. Three possible choices are available for this argument:

• “same”: use the same sign w.r.t. the

  mean direction of the classical longitudinal fields;

• “opposite”: using the opposite sign w.r.t.

  the mean direction of the classical longitudinal fields;

• “random”: using random signs w.r.t. the

  mean direction of the classical longitudinal fields;

Default to random.

Returns

transverse_hfieldsnp.ndarray[float]

The set of random local transverse fields to be added as X-Pauli couplings to the classical spin glass Hamiltonian.

class qtealeaves.optimization.get_exact_driver_product_state(n_sites, bond_dimension=1, numerical_noise=1e-07, tn_type=5, tn_backend=<qtealeaves.tensors.tensor_backend.TensorBackend object>)

Construct the product state

\[{\left\vert+\right\rangle}^{\otimes n}\]

to be used as an initial state for a tensor network ground-state search. Here, \(n\) is the number of sites. This product state is exactly constructed by hand but it can be represented as a tensor network state at a given bond dimension by padding properly the tensors.

Arguments

n_sitesint

The number of physical sites of the tensor network.

bond_dimensionint, optional

The bond dimension of the created product state. Default to 1.

numerical_noisefloat, optional

Numerical noise for creating a product state with bond dimension greater than 1.

tn_typeint, optional

The ansatz to be used for approximating the wave function of the mapped spin glass system. Available topologies are TTN (use 5) for Tree Tensor Networks and MPS (use 6) for Matrix Product States. Default to TTN (5).

tn_backendqtealeaves..tensors.TensorBackend, optional

The backend for the tensors in the the initial tensor network state. Default to TensorBackend().

Returns

psiqtealeaves.emulator.TTN | qtealeaves.emulator.MPS

The created TTN product state. When the tensor network ansatz for the initial state is MPS, the TTN is converted to the corresponding MPS.

class qtealeaves.optimization.get_driver_product_state_via_tn_gss(n_sites, path_to_file, bond_dimension, input_folder=None, output_folder=None, tn_type=5, tn_backend=<qtealeaves.tensors.tensor_backend.TensorBackend object>)

Construct the product state

\[{\left\vert+\right\rangle}^{\otimes n}\]

to be used as an initial state for a tensor network ground-state search. Here, \(n\) is the number of sites. This product state is obtained by performing the ground-state search of the driver Hamiltonian using a bond dimension of bond_dimension.

Arguments

n_sitesint

The number of physical sites of the tensor network.

filenamestr

The full path of the file where the generated product state is stored.

bond_dimensionint, optional

The bond dimension of the created product state. Default to 1.

input_folderstr, optional

The full path to the folder where input data for this ground-state search are stored. Default to None, i.e., a default path will be used.

output_folderstr, optional

The full path to the folder where output data for this ground-state search are stored. Default to None, i.e., a default path will be used.

tn_typeint, optional

The ansatz to be used for approximating the wave function of the mapped spin glass system. Available topologies are TTN (use 5) for Tree Tensor Networks and MPS (use 6) for Matrix Product States. Default to TTN (5).

tn_backendqtealeaves..tensors.TensorBackend, optional

The backend for the tensors in the the initial tensor network state. Default to TensorBackend().

Returns

The full path to the file where the initial tensor-network product state is stored. This file path can be used as a starting point to solve the QUBO problem within the tensor network solver.